1. Field of the Invention
The present invention relates to a method for reconstructing a bar code through consecutive scans.
2. Discussion of Prior Art
As already known, bar codes are largely used in the automatic identification of products.
A bar code is made up of a sequence of light and dark areas which are named space- and bar-type elements. These are rectangular-shaped elements, and each of them can have a different amplitude value. The amplitude of the elements is equal to an elementary value called module, or to multiples of it.
A set of elements univocally represents a character of the code, and a set of characters univocally represents a symbol of a particular code (briefly referred to simply as code). For the purpose of facilitating its location and reading, each code is preceded and followed by quiet zones, that is to say, areas without signs, whose colour corresponds to the background colour on which the bars are printed.
Spaces, quiet zones and background are usually white or, in any case, light, whereas the bars are black or, in any case, dark; this is the case which will be referred to in the following description, for simplicity of exposition. However, the contrary is possible, too.
Each code is defined by a series of rules making up the coding and decoding protocol of that particular type of code. Therefore, a certain sequence of characters matching said protocol represents the decoded symbol of the code being read.
Several methods for scanning and decoding the symbol of a bar code are known. A typical method can be schematised as follows: a device for reading bar codes lights up the code to be decoded along a reading line; the diffused light is collected by a photo-sensor element which, in its turn, generates an analogue signal that is proportional to the intensity of the diffused light.
Bar codes are usually examined according to a scan direction which is not coincident with the longitudinal axis of the code; thus, said scan direction usually forms an angle with the longitudinal axis of the bar code. When this angle exceeds a certain value, only a subset of the elements of the code is scanned; thus, the signal relating to said scan is partial, and it does not allow reading the bar code. Having just partial scans, therefore, there is the problem of xe2x80x9creconstructingxe2x80x9d a complete scan of the code from said partial scans (or, with an abbreviation largely used in the field, xe2x80x9creconstructing the codexe2x80x9d).
In addition, known devices carry out a relative movement between the electro-optical acquisition system of the reader and the objects on which the bar codes are. For example, the electro-optical acquisition system can be of the fixed type, and the objects can be moved, with respect to it, by a movement system, or the reader can be of the portable type, and be moved over the bar codes by an operator.
Other known reconstruction devices are adapted to compose consecutive partial scans, obtained in different positions of the same code, so as to reconstruct and decode the bar code.
Prior-art reconstruction devices may be schematised as in FIG. 2. They use various algorithms, and they are all based on the composition of the characters or of the code elements.
As shown in FIG. 2, the code elements are obtained from the analogue signal, which is obtained by the electro-optical acquisition system, through an operation of digitization. Said digitization essentially consists in squaring the analogue signal, which is reduced to only two values (a high and a low value), and in determining the length of the elements.
The above digitization is a very delicate operation that can generate serious errors in determining the number of elements of the code (by generating errors known as split and merge errors) and in the length of these elements.
For analogue signals affected by faults and distortions such as, for example, blurring, noise and so on, or for reading errors, such as damaged codes or spurious reflexes, the reconstruction and/or the subsequent decoding of the reconstructed code can be compromised.
Therefore, purpose of the present invention is that of realising a method for reconstructing a bar code through consecutive scans to allow a very precise and reliable reconstruction of the code (for its further decoding) with all types of codes, and in particular, with codes whose signals are affected by faults, distortions and reading errors.
According to the invention, this purpose is achieved by a method for reconstructing a bar code through consecutive scans, said bar code being made up of a plurality of elements having a first and a second reflectivity, characterised in that it comprises the following steps:
a) carrying out at least one scan of the bar code;
b) determining a reconstructed wave form, representative of said at least one scan;
c) carrying out an actual scan of the bar code;
d) determining an actual wave form, representative of said actual scan;
e) aligning said reconstructed and actual wave forms;
f) combining said aligned wave forms by updating said reconstructed wave form with said actual wave form.
Herein and in the following description, the term xe2x80x9cscanxe2x80x9d refers to the operation of reading a line through the code. Such operation may be carried out in a number of ways, such as for example illumination with a laser scanner, point by point reading through a photodiode (thus, in a temporal sequence), the contemporaneous illumination of the entire line by a LED and simultaneous global reading through a CCD or C-MOS linear sensor (thus, in a spatial sequence).
The term xe2x80x9cwave formxe2x80x9d refers to the wave form of the analogue signal emitted by the photo-sensor element, possibly processed, but only so that the x-values of the points of the wave form remain directly connected to the temporal or spatial sequence of the different measurement instants or points during a scan.
Differently from the prior art, therefore, the invention can directly operate on the signal of the photo-sensor, before carrying out any digitization of it. This is extremely advantageous because the digitization causes a strong reduction in the information contained in the signal, and said reduction is not recoverable in the following steps. It is also true that usually, the above reduction of information content does not directly hinder the decoding of a bar code, but it has been proved that it can be very disadvantageous during the reconstruction; the reconstruction based on the entire signal is much more precise and reliable for it is based on more information. It must also be taken into account that inaccuracies during the reconstruction often generate errors while decoding.
The aforesaid reconstruction process, with the listed minimum steps from (a) to (f), can be used to combine two or more scans one with another. Preferably, said method is iteratively applied, and thus comprises the following step:
g) iterative repetition of the steps from (c) to (f) until the reconstructed wave form is representative of the entire bar code.
As already said, a very important advantage of the invention is the use of wave forms rich in information content. This information content ensures that it suffices often to use just some properly selected points of the wave forms, and not all of them. In particular, according to a preferred embodiment of the invention, steps (b) and (d) are respectively followed by the following steps:
bxe2x80x2) determining a first series of points on said reconstructed wave form;
dxe2x80x2) determining a second series of points on said actual wave form.
Preferably, said series of points have the same interval, that is to say, each point of the series is separated by an identical distance or by an identical time interval from the following point.
Preferably, the wave forms are analogue, and said series of points are obtained through the sampling of the analogue wave forms.
The number of points provided in each series can be different; preferably, it is of at least 1.5 points for each module of the code to be read. More preferably, it is equal to about 5 points for each module.
Preferably, said series of points are values of brightness expressed in grey scales obtained from an image of the bar code, such as that obtainable with a CCD or C-MOS linear sensor.
The series of points can comprise all the points obtained through the sampling of the analogue wave forms, or preferably, only a subset of them. Said subset, for example and preferably, can comprise:
the maximums and the minimums of the points obtained through the sampling of the analogue wave forms;
the points in which the first derivative of the analogue wave forms crosses zero;
the points in which the second derivative of the analogue wave forms crosses zero.
In an alternative embodiment, the wave forms are two-level digitized wave forms, and said series of points are obtained through the sampling of the two-level digitized wave forms.
Preferably, the alignment step comprises the following steps:
forecasting an expected alignment;
carrying out a rough translation between the two wave forms on the basis of the expected alignment;
calculating a correlation index of the two wave forms;
carrying out a fine translation of a fixed number (M) of steps between the two wave forms in both directions;
calculating the correlation index for each fine translation;
determiningxe2x80x94between the calculated correlation indexesxe2x80x94the index indicative of the minimum difference between the two wave forms;
aligning the two wave forms on the basis of the fine translation to which the determined correlation index corresponds;
updating the expected alignment value on the basis of the above fine alignment.
It has been proved that an alignment thus carried out, allows obtaining a great precision. A fundamental aspect of this preferred method is the use of the correlation index; these terms refer to a number which is calculated according to a comparison of the point-by-point values of the wave forms. It can be a distance index, calculated for example as a function of the summation of values function of the step-by-step difference between the values of the two wave forms; alternatively, it can be a proximity index, function of the summation of values function of the step-by-step product between the values of the two wave forms.
Thanks to the correlation index, it is possible to express the degree of similarity (or of diversity) between the two temporal wave forms with a single numerical value; this approach significantly facilitates the comparisons between wave forms.
Preferably, the calculation of the correlation index only considers the values of the two wave forms that are sufficiently close to one another. The exclusion from the calculation of the values relating to those points of the wave forms that are too different from one other allows not considering the points that are clearly affected by a reading error in at least one of the wave forms; in fact, the difference of the two wave forms caused by said errors does not influence their alignment.
Preferably, the combining step (f) comprises the following steps:
fa) determining a central superimposition area between the aligned reconstructed wave form and the actual wave form, an initial area, in which there is only the reconstructed wave form, and a final area, in which there is only the actual wave form,
fb) selecting, area by area, at least one of said reconstructed and actual wave forms;
fc) updating the reconstructed wave form on the basis of the selected wave form.
More preferably, the selection step (fa) comprises:
in the initial area, point-by-point selection of the value of the reconstructed wave form;
in the central superimposition area, point-by-point selection of a value calculated as a function of the corresponding values of the reconstructed wave form and of the actual wave form;
in the final area, point-by-point selection of the value of the actual wave form.
The calculated value can be obtained in different ways. In an embodiment which is preferred for its simplicity, the calculated value is an average of the corresponding values of the reconstructed wave form and of the actual wave form; this calculation can be easily applied whatever the number of actual wave forms considered for the comparison may be.
However, if the actual wave forms considered are more than one, it can be preferable that the calculated value is chosen through a voting mechanism between the values of the reconstructed and actual wave forms; this means that the most frequent value among those of the different wave forms is chosen point-by-point. More preferably, the differences between the values relating to corresponding points of the wave forms are calculated two by two, whereas the values differing from the others by more than a fixed tolerance are rejected, and the calculated value is chosen as average of the values not rejected.
If the wave form is a two-level digitized wave form, the calculated value can advantageously be chosen through congruence rules with respect to the code syntax. In fact, the two-level digitized wave form actually provides the dimensions of the single elements (bar or space) of the code: in fact, a minimum or maximum value in said wave form means a space or bar element whose length is proportional to the number of points for which this value remains constant. Thus, it is possible and also very easy to check whether the sequences of elements and their lengths are congruent with the syntax of the code being read; the type of code being read can thus be previously known, or it can be determined by decoding the character of initial synchronism.
The method of the invention preferably provides for an initial acquisition step which comprises the following steps:
searching two consecutive wave forms in which there is a portion which can be representative of an end portion of a code preceded and/or followed by a possible quiet zone,
acquiring said wave forms as first and second wave form;
aligning the second wave form with the first wave form;
determining a superimposition area between the second wave form and the first wave form;
carrying out an initial construction of the reconstructed wave form in the superimposition area with data function of the data of the first wave form and of the data of the second wave form;
carrying out an initial construction of the reconstructed wave form in the area following the superimposition area with the data of the second wave form;
carrying out an initial calculation of the expected alignment on the basis of the alignment between the first and the second wave form.
In this way, the reconstruction process starts when something similar to a code is detected; this means, an area in which the wave form presents significant variations of the reflectivity value (possible portion of code) sided by an area in which the reflectivity value is substantially steady (possible quiet zone).
Preferably, the alignment step of the second wave form with the first wave form comprises the following steps:
recognising the apparent quiet zones of the first and second wave form;
carrying out a rough translation between the two wave forms on the basis of their respective apparent quiet zones;
calculating a correlation index of the two wave forms;
carrying out a fine translation between the two wave forms, of a fixed number (M) of steps in both directions;
calculating the correlation index for each of the fine translations;
determiningxe2x80x94between the calculated correlation indexesxe2x80x94the index indicative of the minimum difference between the two wave forms;
aligning the two wave forms on the basis of the fine translation to which the determined correlation index corresponds;
setting the expected alignment value on the basis of the above fine alignment.
In this way, the already explained method of alignment in two steps (rough alignment and fine alignment) is advantageously used also at the initial step of acquisition; in addition, a useful starting value for the expected alignment is obtained.
Preferably, the step of recognition of the apparent quiet zones comprises the following steps:
translating the second wave form with respect to the first wave form on the basis of the two respective possible initial quiet zones;
calculating a correlation index of the two wave forms;
translating the second wave form with respect to the first wave form on the basis of the two respective possible final quiet zones;
calculating a correlation index of the two wave forms;
determiningxe2x80x94between the calculated correlation indexesxe2x80x94the index indicative of the minimum difference between the two wave forms;
recognising as apparent quiet zone of the code the probablexe2x80x94initial or finalxe2x80x94quiet zone that has caused the translation to which the determined correlation index corresponds.
It is thus possible to easily and safely determine whether the two portions of wave form comprise either the beginning or the end of the code by using a correlation index. Preferably, said correlation index is determined according to what previously said about the fine alignment step.